<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>merge stone</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="merge-stone">merge stone</h1>
<ul>
<li>
<ol start="1000">
<li>Minimum Cost to Merge Stones</li>
</ol>
</li>
</ul>
<p>There are N piles of stones arranged in a row.  The i-th pile has stones[i] stones.</p>
<p>A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.</p>
<p>Find the minimum cost to merge all piles of stones into one pile.  If it is impossible, return -1.</p>
<pre><code><code><div>Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.
</div></code></code></pre>
<h1 id="1a-3d-dp-top-to-bottom">1a. 3d dp, top to bottom</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP">https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP</a></li>
</ul>
<p>Intuition
Seem that most of games, especially stone games, are solved by dp?</p>
<p><strong>Explanation</strong></p>
<pre><code><code><div>dp[i][j][m] means the cost needed to merge stone[i] ~ stones[j] into m piles.

Initial status dp[i][i][1] = 0 and dp[i][i][m] = infinity

dp[i][j][1] = dp[i][j][k] + stonesNumber[i][j]
dp[i][j][m] = min(dp[i][mid][1] + dp[mid + 1][j][m - 1])
</div></code></code></pre>
<p><strong>Complexity</strong></p>
<p>Time O(N^3/K), Space O(KN^2)</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeStones</span><span class="hljs-params">(self, stones, K)</span>:</span>
        n = len(stones)
        inf = float(<span class="hljs-string">'inf'</span>)
        prefix = [<span class="hljs-number">0</span>] * (n + <span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            prefix[i + <span class="hljs-number">1</span>] = prefix[i] + stones[i]

        <span class="hljs-keyword">import</span> functools

<span class="hljs-meta">        @functools.lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i, j, m)</span>:</span>
            <span class="hljs-keyword">if</span> (j - i + <span class="hljs-number">1</span> - m) % (K - <span class="hljs-number">1</span>):
                <span class="hljs-keyword">return</span> inf
            <span class="hljs-keyword">if</span> i == j:
                <span class="hljs-keyword">return</span> <span class="hljs-number">0</span> <span class="hljs-keyword">if</span> m == <span class="hljs-number">1</span> <span class="hljs-keyword">else</span> inf
            <span class="hljs-keyword">if</span> m == <span class="hljs-number">1</span>:
                <span class="hljs-keyword">return</span> dp(i, j, K) + prefix[j + <span class="hljs-number">1</span>] - prefix[i]
            <span class="hljs-keyword">return</span> min(dp(i, mid, <span class="hljs-number">1</span>) + dp(mid + <span class="hljs-number">1</span>, j, m - <span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> mid <span class="hljs-keyword">in</span> range(i, j, K - <span class="hljs-number">1</span>))
        res = dp(<span class="hljs-number">0</span>, n - <span class="hljs-number">1</span>, <span class="hljs-number">1</span>)
        <span class="hljs-keyword">return</span> res <span class="hljs-keyword">if</span> res &lt; inf <span class="hljs-keyword">else</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h1 id="1b-3d-dp-bottom-to-top">1b. 3d dp, bottom to top</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247657/JAVA-Bottom-Up-%2B-Top-Down-DP-With-Explaination">https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247657/JAVA-Bottom-Up-%2B-Top-Down-DP-With-Explaination</a></li>
</ul>
<pre><code class="language-python"><div>// Bottom-Up
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> {
    <span class="hljs-title">public</span> <span class="hljs-title">int</span> <span class="hljs-title">mergeStones</span><span class="hljs-params">(int[] stones, int K)</span> {
        <span class="hljs-title">int</span> <span class="hljs-title">len</span> = <span class="hljs-title">stones</span>.<span class="hljs-title">length</span>;
        <span class="hljs-title">if</span> <span class="hljs-params">(<span class="hljs-params">(len - <span class="hljs-number">1</span>)</span> % <span class="hljs-params">(K - <span class="hljs-number">1</span>)</span> != <span class="hljs-number">0</span>)</span> {
            <span class="hljs-title">return</span> -1;
        }
        
        <span class="hljs-title">int</span> <span class="hljs-title">i</span>, <span class="hljs-title">j</span>, <span class="hljs-title">k</span>, <span class="hljs-title">l</span>, <span class="hljs-title">t</span>;
        
        <span class="hljs-title">int</span>[] <span class="hljs-title">prefixSum</span> = <span class="hljs-title">new</span> <span class="hljs-title">int</span>[<span class="hljs-title">len</span> + 1];
        <span class="hljs-title">for</span> <span class="hljs-params">(i = <span class="hljs-number">1</span>; i &lt;= len; i++)</span> {
            <span class="hljs-title">prefixSum</span>[<span class="hljs-title">i</span>] = <span class="hljs-title">prefixSum</span>[<span class="hljs-title">i</span> - 1] + <span class="hljs-title">stones</span>[<span class="hljs-title">i</span> - 1];
        }
        
        <span class="hljs-title">int</span> <span class="hljs-title">max</span> = 99999999;
        <span class="hljs-title">int</span>[][][] <span class="hljs-title">dp</span> = <span class="hljs-title">new</span> <span class="hljs-title">int</span>[<span class="hljs-title">len</span> + 1][<span class="hljs-title">len</span> + 1][<span class="hljs-title">K</span> + 1];
        <span class="hljs-title">for</span> <span class="hljs-params">(i = <span class="hljs-number">1</span>; i &lt;= len; i++)</span> {
            <span class="hljs-title">for</span> <span class="hljs-params">(j = <span class="hljs-number">1</span>; j &lt;= len; j++)</span> {
                <span class="hljs-title">for</span> <span class="hljs-params">(k = <span class="hljs-number">1</span>; k &lt;= K; k++)</span> {
                    <span class="hljs-title">dp</span>[<span class="hljs-title">i</span>][<span class="hljs-title">j</span>][<span class="hljs-title">k</span>] = <span class="hljs-title">max</span>;
                }
            }
        }
        
        <span class="hljs-title">for</span> <span class="hljs-params">(i = <span class="hljs-number">1</span>; i &lt;= len; i++)</span> {
            <span class="hljs-title">dp</span>[<span class="hljs-title">i</span>][<span class="hljs-title">i</span>][1] = 0;
        }

        <span class="hljs-title">for</span> <span class="hljs-params">(l = <span class="hljs-number">2</span>; l &lt;= len; l++)</span> {
            <span class="hljs-title">for</span> <span class="hljs-params">(i = <span class="hljs-number">1</span>; i &lt;= len - l + <span class="hljs-number">1</span>; i++)</span> {
                <span class="hljs-title">j</span> = <span class="hljs-title">i</span> + <span class="hljs-title">l</span> - 1;
                <span class="hljs-title">for</span> <span class="hljs-params">(k = <span class="hljs-number">2</span>; k &lt;= K; k++)</span> {
                    <span class="hljs-title">for</span> <span class="hljs-params">(t = i; t &lt; j; t++)</span> {
                        <span class="hljs-title">dp</span>[<span class="hljs-title">i</span>][<span class="hljs-title">j</span>][<span class="hljs-title">k</span>] = <span class="hljs-title">Math</span>.<span class="hljs-title">min</span><span class="hljs-params">(dp[i][j][k], dp[i][t][k - <span class="hljs-number">1</span>] + dp[t + <span class="hljs-number">1</span>][j][<span class="hljs-number">1</span>])</span>;
                    }
                }

                <span class="hljs-title">dp</span>[<span class="hljs-title">i</span>][<span class="hljs-title">j</span>][1] = <span class="hljs-title">dp</span>[<span class="hljs-title">i</span>][<span class="hljs-title">j</span>][<span class="hljs-title">K</span>] + <span class="hljs-title">prefixSum</span>[<span class="hljs-title">j</span>] - <span class="hljs-title">prefixSum</span>[<span class="hljs-title">i</span> - 1];   
            }
        }

        <span class="hljs-title">return</span> <span class="hljs-title">dp</span>[1][<span class="hljs-title">len</span>][1];
    }
}
</span></div></code></pre>
<h1 id="2-2d-dp">2. 2d dp</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP">https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP</a></li>
</ul>
<p><strong>Explanation</strong></p>
<p>Suggested by @yaoct, we can simplify the third parameter m in DP.</p>
<p>stones[i] ~ stones[j] will merge as much as possible.</p>
<p>Finally (j - i) % (K - 1) + 1 piles will be left.</p>
<p>It's less than K piles and no more merger happens.</p>
<p>dp[i][j] means the minimum cost needed to merge stones[i] ~ stones[j].
dp[i][j] doesn't mean that stone[i]-stone[j] must can be merged into 1 pile. It's just try to merge as much as it can.</p>
<p><strong>Complexity</strong></p>
<p>Time O(N^3/K) Space O(N^2)</p>
<p>It can be improved, but I think it's fine now.</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeStones</span><span class="hljs-params">(self, stones, K)</span>:</span>
        n = len(stones)
        <span class="hljs-keyword">if</span> (n - <span class="hljs-number">1</span>) % (K - <span class="hljs-number">1</span>): <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
        prefix = [<span class="hljs-number">0</span>] * (n + <span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            prefix[i + <span class="hljs-number">1</span>] = prefix[i] + stones[i]

        <span class="hljs-keyword">import</span> functools
<span class="hljs-meta">        @functools.lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i, j)</span>:</span>
            <span class="hljs-keyword">if</span> j - i + <span class="hljs-number">1</span> &lt; K: <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
            res = min(dp(i, mid) + dp(mid + <span class="hljs-number">1</span>, j) <span class="hljs-keyword">for</span> mid <span class="hljs-keyword">in</span> range(i, j, K - <span class="hljs-number">1</span>)) <span class="hljs-comment"># 为什么这里的递增步长是 K-1? 看下面解释</span>
            <span class="hljs-keyword">if</span> (j - i) % (K - <span class="hljs-number">1</span>) == <span class="hljs-number">0</span>:
                res += prefix[j + <span class="hljs-number">1</span>] - prefix[i]
            <span class="hljs-keyword">return</span> res
        <span class="hljs-keyword">return</span> dp(<span class="hljs-number">0</span>, n - <span class="hljs-number">1</span>)
</div></code></pre>
<p><strong>Q: Why mid jump at step K - 1</strong></p>
<pre><code><code><div>A: 
we can't merge K + 1 piles into one pile.
we can merge 1 piles into one pile
we can merge 1 + K - 1 piles into one pile
We can merge 1 + (K - 1)*2 piles into one pile,
We can merge 1 + (K - 1) * steps piles into one pile.

当[3,5,1,2,6]  K=3 的时候，正确答案是25.  但如果递增步长是1, 而不是K-1=2， 会得到错误的答案17

原因是在计算子任务 dp(1,4), 也就是[5,1,2,6]的时候，我们最终需要合并[5,1,2,6]为2个tiles

如果递增步长是1， 那么 dp(1,4) 是下面3种情况的最小值0， 这是错误的， dp(1,2) 和 dp(3,4) 就不应该出现, 他们是不合法的。
dp(1,1)+ dp(2,4) = 9
dp(1,2)+ dp(3,4) = 0
dp(1,3)+ dp(4,4) = 8

如果递增步长是K-1=2， 那么 dp(1,4) 是下面2种情况的最小值8
dp(1,1)+ dp(2,4) = 9
dp(1,3)+ dp(4,4) = 8




</div></code></code></pre>

    </body>
    </html>